package com.ting.test.algorithms.递归和动态规划.样本对应的模型;

import java.util.Stack;

/**
 * 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最长回文子序列是“1234321”或者“123c321”，返回长度7
 *
 * 我们这里的思路就是 先求出该字符串的逆序串
 * 然后 我们认为，如果一个字符串和他的逆序，有公共的子序列，那么这个子序列就是该字符串的回文
 */
public class 最长公共回文解法1 {

    public static void main(String[] args) {
        String str1 = "a12b3c456d";

        int length = maxLength(str1);
    }

    /**
     *
     * @param str1
     * @return
     */
    private static int maxLength(String str1) {
        char[] arr1 = str1.toCharArray();

        Stack<Character> stack = new Stack<Character>();

        // 以下几步的目的是构建一个与str1逆序的字符串
        for (int i = 0; i < str1.length(); i++) {
            stack.push(arr1[i]);
        }

        char[] arr2 = new char[arr1.length];
        for (int i = 0; i < str1.length(); i++) {
            arr2[i] = stack.pop();
        }
        // 这个方法其实就是求最长公共子序列的
        return process(arr1, arr2, arr1.length, arr2.length);
    }


    // str1[0...i]和str2[0...j]，这个范围上最长公共子序列长度是多少？
    // 可能性分类:
    // a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
    // b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
    // c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
    // d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
    // 注意：a)、b)、c)、d)并不是完全互斥的，他们可能会有重叠的情况
    // 但是可以肯定，答案不会超过这四种可能性的范围
    // 那么我们分别来看一下，这几种可能性怎么调用后续的递归。
    // a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
    //    如果是这种情况，那么有没有str1[i]和str2[j]就根本不重要了，因为这两个字符一定没用啊
    //    所以砍掉这两个字符，最长公共子序列 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归)
    // b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
    //    如果是这种情况，那么我们可以确定str2[j]一定没有用，要砍掉；但是str1[i]可能有用，所以要保留
    //    所以，最长公共子序列 = str1[0...i]与str2[0...j-1]的最长公共子序列长度(后续递归)
    // c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
    //    跟上面分析过程类似，最长公共子序列 = str1[0...i-1]与str2[0...j]的最长公共子序列长度(后续递归)
    // d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
    //    同时可以看到，可能性d)存在的条件，一定是在str1[i] == str2[j]的情况下，才成立的
    //    所以，最长公共子序列总长度 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归) + 1(共同的结尾)
    // 综上，四种情况已经穷尽了所有可能性。四种情况中取最大即可
    // 其中b)、c)一定参与最大值的比较，
    // 当str1[i] == str2[j]时，a)一定比d)小，所以d)参与
    // 当str1[i] != str2[j]时，d)压根不存在，所以a)参与
    // 但是再次注意了！
    // a)是：str1[0...i-1]与str2[0...j-1]的最长公共子序列长度
    // b)是：str1[0...i]与str2[0...j-1]的最长公共子序列长度
    // c)是：str1[0...i-1]与str2[0...j]的最长公共子序列长度
    // a)中str1的范围 < b)中str1的范围，a)中str2的范围 == b)中str2的范围
    // 所以a)不用求也知道，它比不过b)啊，因为有一个样本的范围比b)小啊！
    // a)中str1的范围 == c)中str1的范围，a)中str2的范围 < c)中str2的范围
    // 所以a)不用求也知道，它比不过c)啊，因为有一个样本的范围比c)小啊！
    // 至此，可以知道，a)就是个垃圾，有它没它，都不影响最大值的决策
    // 所以，当str1[i] == str2[j]时，b)、c)、d)中选出最大值
    // 当str1[i] != str2[j]时，b)、c)中选出最大值

    /**
     * 该方法的含义是返回arr1[0,arr1Index] 和arr2[0,arr2Index]的最长公共子序列
     * 注意 子序列和子串的区别
     * 子序列是不连续的
     * 子串是字符串中某一段连续的
     * 注意 如果遇到这种两个字符串比较的问题，就通过末尾元素进行比较
     * 一般就是判断末尾元素符不符合要求的几种情况
     *
     * @param arr1
     * @param arr2
     * @param arr1Index 当前字符串1的下标
     * @param arr2Index 当前字符串2的下标
     * @return
     */
    private static int process(char[] arr1, char[] arr2, int arr1Index, int arr2Index) {
        if ((arr1Index == 0) && (arr2Index == 0)) {
            //如果下标都在0位置， 表明当前数组只有一个字符，直接比较二者是否相等
            return arr1[arr1Index] == arr2[arr2Index] ? 1 : 0;
        } else if (arr1Index == 0) {
            // 这里的情况为：
            // str1[0...0]和str2[0...j]，str1只剩1个字符了，但是str2不只一个字符
            // 因为str1只剩一个字符了，所以str1[0...0]和str2[0...j]公共子序列最多长度为1
            // 如果str1[0] == str2[j]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
            // 如果str1[0] != str2[j]，只是此时不相等而已，
            // 那么str2[0...j-1]上有没有字符等于str1[0]呢？不知道，所以递归继续找
            return arr1[arr1Index] == arr2[arr2Index] ? 1 : process(arr1, arr2, arr1Index, arr2Index - 1);
        } else if (arr2Index == 0) {
            return arr1[arr1Index] == arr2[arr2Index] ? 1 : process(arr1, arr2, arr1Index - 1, arr2Index);
        } else {

            //
            //这里则表明 arr1Index和arr2Index 都不在0位置 则考虑几种情况
            //1. arr1和arr2的公共子序列不以arr1Index结尾，但可能以arr2Index结尾 ，可能的含义是可能以arr2Index结尾,也可能不以arr2Index结尾
            // 如果不以arr1Index结尾，则直接可以忽略掉
            int p1 = process(arr1, arr2, arr1Index - 1, arr2Index);
            //2. arr1和arr2的公共子序列不以arr2Index结尾，但可能以arr1Index结尾 ，可能的含义是可能以arr1Index结尾,也可能不以arr1Index结尾
            // 如果不以arr2Index结尾，则直接可以忽略掉
            int p2 = process(arr1, arr2, arr1Index, arr2Index - 1);
            //3. arr1和arr2的公共子序列以arr2Index结尾，也以arr1Index结尾
            // 这里有一个容易忽略的点  我们要求这种情况下以arr2Index结尾，也以arr1Index结尾，就是说arr1[arr1Index] 必须等于 arr2[arr2Index] 否则条件不成立
            int p3 = arr1[arr1Index] == arr2[arr2Index] ? 1 + process(arr1, arr2, arr1Index - 1, arr2Index - 1) : 0;
            return Math.max(p1, Math.max(p2, p3));
        }
    }


    /**
     * 可变参数就是arr1Index 和 arr2Index
     *
     * @param arr1
     * @param arr2
     * @param arr1Index
     * @param arr2Index
     * @return
     */
    private static int dp(char[] arr1, char[] arr2, int arr1Index, int arr2Index) {
        int N = arr1.length;
        int M = arr2.length;
        int[][] dp = new int[N + 1][M + 1];

        dp[0][0] = arr1[arr1Index] == arr2[arr2Index] ? 1 : 0;
        for (int i = 0; i < M; i++) {
            dp[0][i] = arr1[0] == arr2[i] ? 1 : dp[0][i - 1];
        }
        for (int i = 1; i < N; i++) {
            dp[i][0] = arr1[i] == arr2[0] ? 1 : dp[i - 1][0];
        }

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                //
                //这里则表明 arr1Index和arr2Index 都不在0位置 则考虑几种情况
                //1. arr1和arr2的公共子序列不以arr1Index结尾，但可能以arr2Index结尾 ，可能的含义是可能以arr2Index结尾,也可能不以arr2Index结尾
                // 如果不以arr1Index结尾，则直接可以忽略掉
                int p1 = dp[i - 1][j];
                //2. arr1和arr2的公共子序列不以arr2Index结尾，但可能以arr1Index结尾 ，可能的含义是可能以arr1Index结尾,也可能不以arr1Index结尾
                // 如果不以arr2Index结尾，则直接可以忽略掉
                int p2 = dp[i][j - 1];
                //3. arr1和arr2的公共子序列以arr2Index结尾，也以arr1Index结尾
                //
                int p3 = arr1[arr1Index] == arr2[arr2Index] ? 1 + dp[i - 1][j - 1] : 0;
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }
        return dp[N][M];
    }
}
